package letcode.oneQuestionPerDay._202004._09;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: 括号生成
 * @Date: 2020/4/9
 * @Author: 许群星
 */
public class BracketGenerating_a {
    public static void main(String[] args) {
        int a=5;
        int b=3;
        List<String> list=generateParenthesis(b);
//        System.out.println(list.size());
        for (String s:list
             ) {
            System.out.println(s);
        }
    }
    //提供方法     官方题解：暴力法
    //使用递归生成所有序列。遍历序列检查是否有效
    public static List<String> generateParenthesis(int n) {
        List<String> ans=new ArrayList<>();
        generateAll(new char[2*n],0,ans);
        return ans;
    }
    //得到所有的有效的括号序列
    public static void generateAll(char[] current,int pos,List<String> result){
        if (pos==current.length){
            if (valid(current))
                result.add(new String(current));
        }else {
            current[pos]='(';
            generateAll(current,pos+1,result);
            current[pos]=')';
            generateAll(current,pos+1,result);
        }


    }
    //检查括号序列是否有效：遍历，使用变量balance表示左减右的数量。遍历中如果balance小于零，或者结束的时候balance不为零，
    //那么该序列无效，否则有效
    public static boolean valid(char[] current){
        int balance=0;
        for (char c:current
             ) {
            if (c=='(')
                balance++;
            else
                balance--;
            if (balance<0)
                return false;
        }
        return (balance==0);
    }

}
/*
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */